home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / c / objam01.lha / objam / objc / hash.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-12-11  |  5.1 KB  |  182 lines
  1. /*
  2. ** ObjectiveAmiga: Hash tables for Objective C method dispatch
  3. ** See GNU:lib/libobjam/ReadMe for details
  4. */
  5.  
  6.  
  7. #ifndef __hash_INCLUDE_GNU
  8. #define __hash_INCLUDE_GNU
  9.  
  10. #include <stddef.h>
  11.  
  12. /*
  13.  * This data structure is used to hold items
  14.  *  stored in a hash table.  Each node holds 
  15.  *  a key/value pair.
  16.  *
  17.  * Items in the cache are really of type void *.
  18.  */
  19. typedef struct cache_node
  20. {
  21.   struct cache_node *next;    /* Pointer to next entry on the list.
  22.                    NULL indicates end of list. */
  23.   const void *key;        /* Key used to locate the value.  Used
  24.                    to locate value when more than one
  25.                    key computes the same hash
  26.                    value. */
  27.   void *value;            /* Value stored for the key. */
  28. } *node_ptr;
  29.  
  30.  
  31. /*
  32.  * This data type is the function that computes a hash code given a key.
  33.  * Therefore, the key can be a pointer to anything and the function specific
  34.  * to the key type. 
  35.  *
  36.  * Unfortunately there is a mutual data structure reference problem with this
  37.  * typedef.  Therefore, to remove compiler warnings the functions passed to
  38.  * hash_new will have to be casted to this type. 
  39.  */
  40. typedef unsigned int (*hash_func_type)(void *, const void *);
  41.  
  42. /*
  43.  * This data type is the function that compares two hash keys and returns an
  44.  * integer greater than, equal to, or less than 0, according as the first
  45.  * parameter is lexico-graphically greater than, equal to, or less than the
  46.  * second. 
  47.  */
  48.  
  49. typedef int (*compare_func_type)(const void *, const void *);
  50.  
  51.  
  52. /*
  53.  * This data structure is the cache.
  54.  *
  55.  * It must be passed to all of the hashing routines
  56.  *   (except for new).
  57.  */
  58. typedef struct cache
  59. {
  60.   /* Variables used to implement the hash itself.  */
  61.   node_ptr *node_table; /* Pointer to an array of hash nodes.  */
  62.   /* Variables used to track the size of the hash table so to determine
  63.     when to resize it.  */
  64.   unsigned int size; /* Number of buckets allocated for the hash table
  65.             (number of array entries allocated for
  66.             "node_table").  Must be a power of two.  */
  67.   unsigned int used; /* Current number of entries in the hash table.  */
  68.   unsigned int mask; /* Precomputed mask.  */
  69.  
  70.   /* Variables used to implement indexing through the hash table.  */
  71.  
  72.   unsigned int last_bucket; /* Tracks which entry in the array where
  73.                    the last value was returned.  */
  74.   /* Function used to compute a hash code given a key. 
  75.      This function is specified when the hash table is created.  */
  76.   hash_func_type    hash_func;
  77.   /* Function used to compare two hash keys to see if they are equal.  */
  78.   compare_func_type compare_func;
  79. } *cache_ptr;
  80.  
  81.  
  82. /* Two important hash tables.  */
  83. extern cache_ptr module_hash_table, class_hash_table;
  84.  
  85. /* Allocate and initialize a hash table.  */ 
  86.  
  87. cache_ptr hash_new (unsigned int size,
  88.             hash_func_type hash_func,
  89.             compare_func_type compare_func);
  90.                        
  91. /* Deallocate all of the hash nodes and the cache itself.  */
  92.  
  93. void hash_delete (cache_ptr cache);
  94.  
  95. /* Add the key/value pair to the hash table.  If the
  96.    hash table reaches a level of fullnes then it will be resized. 
  97.                                                    
  98.    assert if the key is already in the hash.  */
  99.  
  100. void hash_add (cache_ptr *cachep, const void *key, void *value);
  101.      
  102. /* Remove the key/value pair from the hash table.  
  103.    assert if the key isn't in the table.  */
  104.  
  105. void hash_remove (cache_ptr cache, const void *key);
  106.  
  107. /* Used to index through the hash table.  Start with NULL
  108.    to get the first entry.
  109.                                                   
  110.    Successive calls pass the value returned previously.
  111.    ** Don't modify the hash during this operation *** 
  112.                                                   
  113.    Cache nodes are returned such that key or value can
  114.    be extracted.  */
  115.  
  116. node_ptr hash_next (cache_ptr cache, node_ptr node);
  117.  
  118. /* Used to return a value from a hash table using a given key.  */
  119.  
  120. void *hash_value_for_key (cache_ptr cache, const void *key);
  121.  
  122.  
  123. /************************************************
  124.  
  125.         Useful hashing functions.  
  126.         
  127.         Declared inline for your pleasure.
  128.         
  129. ************************************************/
  130.  
  131. /* Calculate a hash code by performing some 
  132.    manipulation of the key pointer.  (Use the lowest bits
  133.    except for those likely to be 0 due to alignment.)  */
  134.  
  135. static inline unsigned int
  136. hash_ptr (cache_ptr cache, const void *key)
  137. {
  138.   return ((size_t)key / sizeof (void *)) & cache->mask;
  139. }
  140.  
  141.  
  142. /* Calculate a hash code by iterating over a NULL 
  143.    terminate string.  */
  144. static inline unsigned int 
  145. hash_string (cache_ptr cache, const void *key)
  146. {
  147.   unsigned int ret = 0;
  148.   unsigned int ctr = 0;
  149.         
  150.         
  151.   while (*(char*)key) {
  152.     ret ^= *(char*)key++ << ctr;
  153.     ctr = (ctr + 1) % sizeof (void *);
  154.   }
  155.  
  156.   return ret & cache->mask;
  157. }
  158.  
  159.  
  160. /* Compare two pointers for equality.  */
  161. static inline int 
  162. compare_ptrs (const void *k1, const void *k2)
  163. {
  164.   return !(k1 - k2);
  165. }
  166.  
  167.  
  168. /* Compare two strings.  */
  169. static inline int 
  170. compare_strings (const void *k1, const void *k2)
  171. {
  172.   if (k1 == k2)
  173.     return 1;
  174.   else if (k1 == 0 || k2 == 0)
  175.     return 0;
  176.   else
  177.     return !strcmp (k1, k2);
  178. }
  179.  
  180.  
  181. #endif /* not __hash_INCLUDE_GNU */
  182.